// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/base/lookup_string_in_fixed_set.h"

#include "base/logging.h"

namespace net {

namespace {

    // Read next offset from pos.
    // Returns true if an offset could be read, false otherwise.
    bool GetNextOffset(const unsigned char** pos,
        const unsigned char* end,
        const unsigned char** offset)
    {
        if (*pos == end)
            return false;

        // When reading an offset the byte array must always contain at least
        // three more bytes to consume. First the offset to read, then a node
        // to skip over and finally a destination node. No object can be smaller
        // than one byte.
        CHECK_LT(*pos + 2, end);
        size_t bytes_consumed;
        switch (**pos & 0x60) {
        case 0x60: // Read three byte offset
            *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
            bytes_consumed = 3;
            break;
        case 0x40: // Read two byte offset
            *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
            bytes_consumed = 2;
            break;
        default:
            *offset += (*pos)[0] & 0x3F;
            bytes_consumed = 1;
        }
        if ((**pos & 0x80) != 0) {
            *pos = end;
        } else {
            *pos += bytes_consumed;
        }
        return true;
    }

    // Check if byte at offset is last in label.
    bool IsEOL(const unsigned char* offset, const unsigned char* end)
    {
        CHECK_LT(offset, end);
        return (*offset & 0x80) != 0;
    }

    // Check if byte at offset matches first character in key.
    // This version matches characters not last in label.
    bool IsMatch(const unsigned char* offset,
        const unsigned char* end,
        const char* key)
    {
        CHECK_LT(offset, end);
        return *offset == *key;
    }

    // Check if byte at offset matches first character in key.
    // This version matches characters last in label.
    bool IsEndCharMatch(const unsigned char* offset,
        const unsigned char* end,
        const char* key)
    {
        CHECK_LT(offset, end);
        return *offset == (*key | 0x80);
    }

    // Read return value at offset.
    // Returns true if a return value could be read, false otherwise.
    bool GetReturnValue(const unsigned char* offset,
        const unsigned char* end,
        int* return_value)
    {
        CHECK_LT(offset, end);
        if ((*offset & 0xE0) == 0x80) {
            *return_value = *offset & 0x0F;
            return true;
        }
        return false;
    }

} // namespace

// Lookup a domain key in a byte array generated by make_dafsa.py.
// The rule type is returned if key is found, otherwise kDafsaNotFound is
// returned.
int LookupStringInFixedSet(const unsigned char* graph,
    size_t length,
    const char* key,
    size_t key_length)
{
    const unsigned char* pos = graph;
    const unsigned char* end = graph + length;
    const unsigned char* offset = pos;
    const char* key_end = key + key_length;
    while (GetNextOffset(&pos, end, &offset)) {
        //   char <char>+ end_char offsets
        //   char <char>+ return value
        //   char end_char offsets
        //   char return value
        //   end_char offsets
        //   return_value
        bool did_consume = false;
        if (key != key_end && !IsEOL(offset, end)) {
            // Leading <char> is not a match. Don't dive into this child
            if (!IsMatch(offset, end, key))
                continue;
            did_consume = true;
            ++offset;
            ++key;
            // Possible matches at this point:
            // <char>+ end_char offsets
            // <char>+ return value
            // end_char offsets
            // return value
            // Remove all remaining <char> nodes possible
            while (!IsEOL(offset, end) && key != key_end) {
                if (!IsMatch(offset, end, key))
                    return kDafsaNotFound;
                ++key;
                ++offset;
            }
        }
        // Possible matches at this point:
        // end_char offsets
        // return_value
        // If one or more <char> elements were consumed, a failure
        // to match is terminal. Otherwise, try the next node.
        if (key == key_end) {
            int return_value;
            if (GetReturnValue(offset, end, &return_value))
                return return_value;
            // The DAFSA guarantees that if the first char is a match, all
            // remaining char elements MUST match if the key is truly present.
            if (did_consume)
                return kDafsaNotFound;
            continue;
        }
        if (!IsEndCharMatch(offset, end, key)) {
            if (did_consume)
                return kDafsaNotFound; // Unexpected
            continue;
        }
        ++key;
        pos = ++offset; // Dive into child
    }
    return kDafsaNotFound; // No match
}

} // namespace net
